#include <stdio.h>
#include <limits.h>


// 贪心
int maxProfit(int* prices, int pricesSize)
{
    int profit = 0;
    //int last_profit = 0;

    for (int i = 1; i < pricesSize; i++) {
        int day_profit = prices[i] - prices[i-1];
        if (day_profit > 0)
            profit += day_profit;
    }
    return profit;
}

// backtracking method
void dfs(int* prices, int pricesSize, int *ans, int profit, int take_stock, int day) {
    if (day == pricesSize) {
        if (profit > *ans)
            *ans = profit;
        return;
    }

    if (take_stock != -1) {
        for (int i = day; i < pricesSize; i++) {
            if (prices[i] > take_stock) {
                profit += (prices[i] - take_stock);
                dfs(prices, pricesSize, ans, profit, -1, i+1);
                profit -= (prices[i] - take_stock);
            }
        }
    } else {
        for (int i = day; i < pricesSize; i++) {
            dfs(prices, pricesSize, ans, profit, prices[i], i+1);
        }
    }
}

int maxProfit2(int* prices, int pricesSize) {
    static int ans = 0;
    ans = 0;
    if (pricesSize < 2)
        return 0;

    dfs(prices, pricesSize, &ans, 0, -1, 0);
    return ans;
}

int main(void)
{
    printf("#122. 买卖股票的最佳时机 II\n");
    printf("https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/\n");
    printf("这个题目，常规解法应该是暴力（不能AC）或动态规划，贪心有点取巧和特殊\n");
    int nums[] = {1,2,3,4,5};
    //int nums[] = {-2};
    int ret = maxProfit(nums, sizeof(nums)/sizeof(int));
    printf("ret : %d\n", ret);

    ret = maxProfit2(nums, sizeof(nums)/sizeof(int));
    printf("\n\nret : %d\n", ret);
}

